﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace DoAnTriTueNhanTao
{
    class UCS
    {
        // Ma trận đầu vào lưu các cạnh và trọng số của đồ thị.
        MatrixInput matrixInput;
        // Số đỉnh của đồ thị hiện tại.
        int iN;
        // Mảng đánh dấu 1 đỉnh đã được xét chưa (trong Lý thuyết là từng được đưa vào hàng đợi hay chưa): bPushed[i] = false là đỉnh i chưa được xét và ngược lại.
        bool[] bPushed;
        // Mảng lưu chi phí ít nhất hiện tại để đi đến một đỉnh: iCost[i] là chi phí ít nhất (hiện tại) để đi từ đỉnh bắt đầu đến đỉnh i.
        int[] iCost;
        // Mảng lưu vị trí đỉnh quay lui: iBack[i] là đỉnh trước đó của đỉnh i trên đường đi ngắn nhất từ đỉnh bắt đầu đến đỉnh i.
        int[] iBack;

        int i = 0; // Biến chạy.

        public UCS()
        {
            // Khởi tạo ma trận đầu vào.
            matrixInput = new MatrixInput();
            // Khởi tạo ma trận mẫu để thực hiện thuật toán.
            matrixInput.makeSampleInput();

            iN = matrixInput.nPoint; // Số đỉnh của ma trận.

            // Khởi tạo mảng đánh dấu 1 đỉnh đã được xét chưa.
            bPushed = new bool[iN];
            // Tất cả các đỉnh ban đầu đều chưa được duyệt.
            for (i = 0; i < iN; i++)
            {
                bPushed[i] = false;
            }

            // Khởi tạo mảng lưu chi phí ít nhất hiện tại để đi đến một đỉnh.
            iCost = new int[iN];
            // Tất cả các chi phí đều là vô cùng (-1).
            for (i = 0; i < iN; i++)
            {
                iCost[i] = -1;
            }

            // Khởi tạo mảng lưu vị trí đỉnh quay lui.
            iBack = new int[iN];
            // Tất cả đỉnh đều ko có đỉnh quay lui.
            for (i = 0; i < iN; i++)
            {
                iBack[i] = -1;
            }
        }

        public string doingUCS(int iStart, int iEnd)
        {
            // Cập nhập lại mảng lưu chi phí ít nhất từ đỉnh bắt đầu đến mỗi đỉnh.
            for (i = 0; i < iN; i++)
            {
                iCost[i] = matrixInput.matrix[iStart, i]; // Chi phí ít nhất từ đỉnh bắt đầu iStart đến mỗi đỉnh i ban đầu chính là cạnh nối iStart đến đỉnh i.
                // Nếu không có cạnh nối thì chi phí bằng không.
                //if (iCost[i] == -1)
                //    iCost[i] = 0;
                iBack[i] = iStart;
            }

            int iU = -1; // Đỉnh có chi phí nhỏ nhất trong quá trình chạy UCS.
            int iMin; // Chi phí nhỏ nhất.

            iCost[iStart] = 0; // Chi phí ít nhất đi từ iStart đến iStart là 0.
            bPushed[iStart] = true; // Đánh dấu điểm iStart đã xét.
            iBack[iStart] = -1; //

            // Trong khi điểm iEnd chưa được xét.
            while (!bPushed[iEnd])
            {
                iMin = -1; // Chi phí nhỏ nhất hiện giờ là rất lớn (quy ước -1).

                // Tìm trạng thái chi phí thấp nhất trong các đỉnh đang được xét (đang nằm trong hàng đợi ưu tiên).
                for(i = 0; i < iN; i++)
                    if ((bPushed[i]) && (iMin == -1 || (iCost[i] != -1 && iMin > iCost[i])))
                    {
                        iMin = iCost[i];
                        iU = i;
                    }

                // Nếu tìm thấy thì lấy đỉnh có trạng thái chi phí thấp nhất ra khỏi hàng đợi ưu tiên.
                if (iMin != -1)
                    bPushed[iU] = false;

                // Nếu đỉnh kết thúc vẫn chưa được đánh dấu.
                if (!bPushed[iEnd])
                {
                    // Thêm các đỉnh con vào trong hàng đợi ưu tiên.
                    for (i = 0; i < iN; i++)
                        // Nếu điểm tiếp theo đã xét và đủ điều kiện để độ ưu tiên thay đổi thì mới cập nhập độ ưu tiên (đường đi tốt hơn đường đi đã biết trước đó).
                        // Hoặc là nếu điểm tiếp theo chưa bao giờ được xét (đưa vào hàng đợi) thì cũng thêm vào.
                        if (matrixInput.matrix[iU, i] != -1 && ((bPushed[i] == true && iCost[i] > iCost[iU] + matrixInput.matrix[iU, i]) || (bPushed[i] == false)))
                        {
                            bPushed[i] = true;
                            iCost[i] = iCost[iU] + matrixInput.matrix[iU, i];
                            iBack[i] = iU;
                        }
                }
            }

            // Lưu kết quả chuỗi kết quả để xuất ra MessageBox cho dễ thấy vì chưa thiết kế cách thức xuất kết quả.
            string str = "";

            // Nếu đỉnh iEnd đã được xét.
            if (bPushed[iEnd])
            {
                // Điểm bắt đầu trùng với điểm kết thúc: đường đi ngắn nhất bằng 0.
                if (iStart == iEnd)
                {
                    str = str + "Chi phí: 0\nTruy ngược đường đi:\nĐỉnh " + iStart.ToString() + "\n";
                }
                else
                {
                    // Xuất ra chi phí đường đi ngắn nhất tìm được.
                    str = str + "Chi phí: " + iCost[iEnd].ToString() + "\nTruy ngược đường đi:\n" + "Đỉnh " + iEnd.ToString() + "\n";
                    i = iBack[iEnd];
                    while (i != iStart && i != -1)
                    {
                        // Tra các đỉnh quay lui của đỉnh hiện tại để có được các đỉnh lần lượt trên đường đi ngắn nhất (thứ tự ngược).
                        str = str + "Đỉnh " + i.ToString() + "\n";
                        i = iBack[i];
                    }
                    // Đỉnh bắt đầu.
                    str = str + "Đỉnh " + iStart.ToString() + "\n";
                }
            }
            else
            {
                str = "Không tìm thấy đường đi ngắn nhất.";
            }

            return str;
        }
    }
}
